package cn.wolfcode.sort;

import java.util.Arrays;
import java.util.Random;

public class Sort {

    public static void quickSort(int[] arr,int left,int right){
        if(left >= right){
            return;
        }
        //左指针i，右指针j
        int i = left;
        int j = right;
        int indexNum = arr[left];
        while(i != j){
            while(indexNum <= arr[j] && i < j){
                j--;
            }
            while(indexNum >= arr[i] && i < j){
                i++;
            }
            if(i < j){
                int temp = arr[j];
                arr[j] = arr[i];
                arr[i] = temp;
            }
        }
        //指针相遇
        arr[left] = arr[i];
        arr[i] = indexNum;

        //左子数组
        quickSort(arr,left,i-1);
        //右子数组
        quickSort(arr,j+1,right);
    }

    public static void main(String[] args) {
        int[] arr = getRandomArr(20, 10);
        System.out.println(Arrays.toString(arr));
        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));

    }

    // 随机生成数组
    public static int[] getRandomArr(int bound, int length) {
        int[] arr = new int[length];
        Random random = new Random();
        for (int i = 0; i < length; i++) {
            arr[i] = random.nextInt(bound);
        }
        return arr;
    }

}
